from typing import Optional

from com.example.leetcode.tree.common.TreeUtils import TreeNode, generate_binary_tree


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0

            # 左右子树的最大贡献值，若为负则视为 0（不选）
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)

            # 当前节点最大路径和 = 左 + 右 + 自己（可能为“拐弯路径”）
            current_max = node.val + left_gain + right_gain

            # 更新全局最大值
            self.max_sum = max(self.max_sum, current_max)

            # 向上传递的最大路径 = 自己 + max(左, 右)
            return node.val + max(left_gain, right_gain)

        dfs(root)
        return self.max_sum


if __name__ == '__main__':
    s = Solution()
    nums = [-10, 9, 20, None, None, 15, 7]
    root = generate_binary_tree(nums)
    print(s.maxPathSum(root))
